<!DOCTYPE html>
<html>

<head>
	<meta charset="utf-8">
	<title>Box guessing game calculator</title>
	<style>
		body {
			background-color: #000;
			color: #FFF;
			display: flex;
			flex-direction: column;
			justify-content: center;
			align-items: center;
			font-family: Bahnschrift;
		}

		input,
		textarea {
			background-color: inherit !important;
			color: inherit !important;
			border: 1px solid #888;
			border-radius: 0px;
		}

		input {
			height: 25px;
			font-family: inherit !important;
		}

		th,
		td {
			margin: 10px;
		}
	</style>
</head>

<body>
	<h1>Box guessing game calculator</h1>
	<h2># of boxes:<input id="m" type="number" min="0" value="4"></h2>
	<h2># of shields:<input id="n" type="number" min="0" value="8"></h2>
	<h2>Precision:<input id="p" type="number" min="0" value="1"></h2>
	<h1>Result:</h1>
	<table style="text-align: center;">
		<thead>
			<tr id="tableHead">
				<th># of boxes</th>
			</tr>
		</thead>
		<tbody id="tableBody">
		</tbody>
	</table>
</body>
<script>
	function solve(n, m) {
		let inverseM = 1 / m

		let optimal = new Array(n + 1)
		optimal[0] = 0
		let max = new Array(n + 1)
		max[0] = 0
		let distribution = new Array(n + 1)
		distribution[0] = [1]
		let decisions = new Array(n + 1)
		decisions[0] = [{ expected: 0, distribution: [1] }]

		for (let i = 1; i <= n; ++i) {
			let maxM = (i < m) ? i : m
			let decisionI = new Array(maxM + 1)
			let maxI = -1
			let optimalI = undefined
			for (let j = maxM; j; --j) {
				let prob = j * inverseM
				let expected = prob * (1 + max[i - j])
				let distributionI = [1 - prob]
				distribution[i - j].forEach(function (x) {
					distributionI.push(x * prob)
				})
				decisionI[j] = {
					expected: expected,
					distribution: distributionI
				}
				if (expected > maxI) {
					maxI = expected
					optimalI = j
				}
			}
			decisionI[0] = { expected: 0, distribution: [1] }
			max[i] = maxI
			optimal[i] = optimalI
			distribution[i] = decisionI[optimalI].distribution
			decisions[i] = decisionI
		}

		return {
			max: max,
			optimal: optimal,
			distribution: distribution,
			decisions: decisions
		}
	}
	function display(n, m, p) {
		let result = solve(n, m)

		let tableColumns = (n < m) ? n : m
		let tableHead = document.getElementById('tableHead')
		tableHead.innerHTML = ''
		let headI = document.createElement('th')
		headI.innerHTML = '# of shields'
		tableHead.appendChild(headI)

		for (let i = 0; i <= tableColumns; ++i) {
			let heading = document.createElement('th')
			heading.innerHTML = i ? ((i == 1) ? 'Use 1 shield' : 'Use ' + i.toString() + ' shields') : 'Use no shield'
			tableHead.appendChild(heading)
		}

		let tableBody = document.getElementById('tableBody')
		tableBody.innerHTML = ''
		for (let i = 0; i <= n; ++i) {
			let row = document.createElement('tr')
			let dataI = document.createElement('td')
			dataI.innerHTML = i.toString()
			row.appendChild(dataI)

			let optimalI = result.optimal[i]
			let decisionI = result.decisions[i]
			for (let j = 0; j <= tableColumns; ++j) {
				let data = document.createElement('td')
				if (j <= i) {
					let d = decisionI[j]
					let dis = d.distribution
					let disString = ''
					dis.forEach(function (x, k) {
						disString += k + ':' + (x * 100).toFixed(p) + '% '
					})
					disString += '≥' + dis.length + ':0%'
					data.innerHTML = '<p>' + d.expected.toFixed(p) + '</p><p>' + disString + '</p>'
				} else {
					data.innerHTML = 'N/A'
				}
				if (j == optimalI) {
					data.style.backgroundColor = '#080'
					data.style.color = '#000'
				}
				row.appendChild(data)
			}
			tableBody.appendChild(row)
		}
	}
	function update() {
		let n = parseInt(document.getElementById('n').value)
		let m = parseInt(document.getElementById('m').value)
		let p = parseInt(document.getElementById('p').value)
		display(n, m, p)
	}
	update()
	document.getElementById('n').addEventListener('input', update)
	document.getElementById('m').addEventListener('input', update)
	document.getElementById('p').addEventListener('input', update)
</script>

</html>